package leetcode.easy.q14;

/**
 * Q 14 找最长公共前缀
 */
public class Question {
    public static void main(String[] args) {
        System.out.printf(String.format("longestCommonPrefix:%s",new Solution2().longestCommonPrefix(new String[]{"aa","ab","ac"})));
    }
}

/**
 * 最长公共前缀，找到最小字符串，然后不断裁剪直到匹配完成
 */
class Solution2 {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        String str = minStr(strs);
        for (String s : strs) {
            while (!s.startsWith(str)) {
                if (str.length() == 0) return "";
                str = str.substring(0, str.length() - 1);
            }
        }
        return str;
    }

    /**
     * 找到最短的字符串，以期望在后续substring执行最少次数
     */
    private String minStr(String[] strings) {
        String min = strings[0];
        for (String str : strings) {
            if (str.length() < min.length()) {
                min = str;
            }
        }
        return min;
    }
}

/**
 * 最长公共前缀，一位字符一位字符的比较
 */
class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        if (strs.length == 1) {
            return strs[0];
        }
        int minLength = minLength(strs);
        int endIndex = -1;
        for (int i = 0; i < minLength; i++) {
            boolean match = true;
            for (int index = 0; index < strs.length - 1; index++) {
                if (strs[index].charAt(i) != strs[index + 1].charAt(i)) {
                    match = false;
                }

            }
            if (match) {
                endIndex = i;
            } else {
                break;
            }
        }
        return strs[0].substring(0, endIndex + 1);
    }

    private int minLength(String[] strings) {
        int min = 201;
        for (String str : strings) {
            if (str.length() < min) {
                min = str.length();
            }
        }
        return min;
    }

}


